package com.chb.mains;

import java.util.*;

/**
 * @description:
 * @author: CHB
 * @create: 2022-04-09 15:20
 **/
public class SolutionBarcode {
    /**
     * 在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。
     *
     * 请你重新排列这些条形码，使其中任意两个相邻的条形码不能相等。 你可以返回任何满足该要求的答案，此题保证存在答案。
     * 示例 1：
     * 输入：barcodes = [1,1,1,2,2,2]
     * 输出：[2,1,2,1,2,1]
     */
     public int[] rearrangeBarcodes(int[] barcodes) {
            int len = barcodes.length;
            Map<Integer,Integer> map = new TreeMap<>();
            List<Map.Entry<Integer,Integer>> list = new ArrayList<>();
            for (int i = 0; i < len; i++){
                map.merge(barcodes[i],1,Integer::sum);
            }
            for(Map.Entry<Integer,Integer> entry : map.entrySet()){
                list.add(entry);
            }
            list.sort(Comparator.comparingInt(Map.Entry::getValue));
            int index = list.size() - 1;
            for (int i = 0; i < len; i+=2){
                int value = list.get(index).getValue();
                int key = list.get(index).getKey();
                if(value > 0){
                    barcodes[i] = key;
                    map.replace(key, value - 1);
                }else{
                    index -= 1;
                    value = list.get(index).getValue();
                    key = list.get(index).getKey();
                    barcodes[i] = key;
                    map.replace(key, value - 1);
                }
            }
            for (int i = 1; i < len; i+=2){
                int value = list.get(index).getValue();
                int key = list.get(index).getKey();
                if(value > 0){
                    barcodes[i] = key;
                    map.replace(key, value - 1);
                }else{
                    index -= 1;
                    value = list.get(index).getValue();
                    key = list.get(index).getKey();
                    barcodes[i] = key;
                    map.replace(key, value - 1);
                }
            }

            return barcodes;
        }
}